The maximum matching of a bipartite graph is the matroid crossing of a partitioned matroid pair
from matroid
The maximum matching of a bipartite graph is the matroid crossing of a partitioned matroid pair
https://gyazo.com/a370998bd984fe19e25da836e8ab653f
Focusing on the V1 side vertex, only one edge at most comes out of one vertex.
That is, split matroid.
Same for V2 side
The edge set that is matching is a common subset of these two
In other words matroid crossing.
https://app.mathsoc.jp/meeting_data/tokyo18mar/pdf/msjmeeting-2018mar-00f004.pdf
matroid crossing
incremental algorithm
The Maximum matching problem on 2-part graph is a split matroid pair crossing problem
---
This page is auto-translated from /nishio/2部グラフの最大マッチングは，分割マトロイド対のマトロイド交叉. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.